// @algorithm @lc id=63 lang=cpp 
// @title unique-paths-ii


// @test([[0,0,0],[0,1,0],[0,0,0]])=2
// @test([[0,1],[0,0]])=1
class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        if(obstacleGrid[0][0] || obstacleGrid.back().back()) return 0;
        int m = obstacleGrid.size(), n = obstacleGrid[0].size();
        vector<int> dp(n, 0); dp[0] = 1;
        for(int i=0; i<m; i++){
            dp[0] = (dp[0] && !obstacleGrid[i][0]);
            for(int j=1; j<n; j++){
                if(obstacleGrid[i][j]){
                    dp[j] = 0;
                    continue;
                }
                if(!obstacleGrid[i][j-1])
                    dp[j] += dp[j-1];
            }
        }
        return dp[n-1];
    }
};